package com.zy.GA;

import java.util.*;

public class GeneticsAlgorithm {
    // Define problem parameters
    private static final int[][] items = {
            {4, 12},
            {2, 2},
            {6, 10},
            {1, 1},
            {2, 4},
            {3, 1},
            {5,7},
            {3,2},
            {8,18},
            {4,9}

    };
    private static final int MAX_WEIGHT = 15;

    // Define genetic algorithm parameters
    private static final int POPULATION_SIZE = 50;
    private static final int GENERATIONS = 100;
    private static final double MUTATION_RATE = 0.1;

    private  static  int best=0;
    // Define fitness function
    private static int fitness(int[] individual) {
        int totalWeight = 0;
        int totalValue = 0;
        for (int i = 0; i < individual.length; i++) {
            if (individual[i] == 1) {
                totalWeight += items[i][0];
                totalValue += items[i][1];
            }
        }
        if (totalWeight > MAX_WEIGHT) {
            return 0;
        } else {
            return totalValue;
        }
    }

    // 选择函数
    private static int[][] selection(int[][] population) {
        int[][] parents = new int[2][population[0].length];
        int[] fitnesses = new int[POPULATION_SIZE];
        int totalFitness = 0;
        for (int i = 0; i < POPULATION_SIZE; i++) {
            fitnesses[i] = fitness(population[i]);
            totalFitness += fitnesses[i];
        }
        for (int j = 0; j < 2; j++) {
            int r = new Random().nextInt(totalFitness);
            int sum = 0;
            for (int i = 0; i < POPULATION_SIZE; i++) {
                sum += fitnesses[i];
                if (sum > r) {
                    parents[j] = population[i];
                    break;
                }
            }
        }
        return parents;
    }

    // 交叉函数
    private static int[][] crossover(int[][] parents) {
        int[] child1 = new int[parents[0].length];
        int[] child2 = new int[parents[0].length];
        int crossoverPoint = new Random().nextInt(parents[0].length);//交叉点
        for (int i = 0; i < crossoverPoint; i++) {
            child1[i] = parents[0][i];
            child2[i] = parents[1][i];
        }
        for (int i = crossoverPoint; i < parents[0].length; i++) {
            child1[i] = parents[1][i];
            child2[i] = parents[0][i];
        }
        return new int[][]{child1, child2};
    }

    // 突变函数
    private static int[] mutation(int[] child) {
        for (int i = 0; i < child.length; i++) {
            if (new Random().nextDouble() < MUTATION_RATE) {
                child[i] = 1 - child[i]; //1-0=1，1-1=0
            }
        }
        return child;
    }

    public static void main(String[] args) {
        long starttime = System.currentTimeMillis();

        // Initialize population
        int[][] population = new int[POPULATION_SIZE][items.length];
        for (int i = 0; i < POPULATION_SIZE; i++) {
            for (int j = 0; j < items.length; j++) {
                population[i][j] = new Random().nextInt(2);
            }
        }

        // Main loop
        for (int generation = 0; generation < GENERATIONS; generation++) {
            // Select parents and generate new population
            int[][] newPopulation = new int[POPULATION_SIZE][items.length];
            for (int i = 0; i < POPULATION_SIZE; i += 2) {
                int[][] parents = selection(population);//选择
                int[][] children = crossover(parents);
                int[] child1 = mutation(children[0]);
                int[] child2 = mutation(children[1]);
                newPopulation[i] = child1;
                newPopulation[i + 1] = child2;
            }
            // Replace old population with new population
            population = newPopulation;
            // Print best individual in each generation
                int bestFitness=0;
            for (int i = 0; i < POPULATION_SIZE; i++) {
                int fitness = fitness(population[i]);
                if (fitness > bestFitness) {
                    bestFitness = fitness;
                }
            }
            if(bestFitness>best){
                best=bestFitness;
            }
            System.out.println("Generation " + (generation+1) + ": Best fitness = " + bestFitness);
        }
        System.out.println("----------");
        System.out.println("best"+best);
    }
}
